package com.mlh.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/8/21 16:43
 * @DESCRIPTION
 */
// 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
// 实现 LRUCache 类：
// LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
// 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
public class LRU缓存 {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    Map<Integer, DLinkedNode> map = new HashMap<>();
    private int capacity;
    private int size;
    private DLinkedNode headSentry, tailSentry;

    public LRU缓存(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        // 使用头部和尾部哨兵节点
        headSentry = new DLinkedNode();
        tailSentry = new DLinkedNode();
        headSentry.next = tailSentry;
        tailSentry.prev = headSentry;
    }

    public int get(int key) {
        DLinkedNode cur = map.get(key);
        if(cur==null){
            return -1;
        }
        moveToHead(cur);
        return cur.value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){//如果存在
            DLinkedNode cur = map.get(key);
            cur.value=value;
            moveToHead(cur);
        }else {//如果不存在,加入到链表头，并加入到map中
            if(size==capacity){//满了，删除最后一个节点，并在map中删除该节点
                DLinkedNode deleteNode = deleteTail();
                map.remove(deleteNode.key);
            }
            //插入新节点
            DLinkedNode cur = new DLinkedNode(key, value);
            //加入到map中
            map.put(key,cur);
            //接在头结点处
            cur.next=headSentry.next;
            cur.prev=headSentry;
            headSentry.next.prev=cur;
            headSentry.next=cur;
            size++;//节点数++
        }

    }

    //将已存在链表中的节点移到头部
    private void moveToHead(DLinkedNode cur){
        cur.prev.next=cur.next;
        cur.next.prev=cur.prev;
        cur.next=headSentry.next;
        headSentry.next.prev=cur;
        cur.prev=headSentry;
        headSentry.next=cur;
    }

    private DLinkedNode deleteTail(){
        DLinkedNode last=tailSentry.prev;
        tailSentry.prev=tailSentry.prev.prev;
        tailSentry.prev.next=tailSentry;
        size--;
        return last;
    }
}
